package TPO_Progra_III;

import Implementaciones.Conjunto;
import TDA.ConjuntoTDA;
import TDA.MatrizTDA;

public class Sudoku {
	
	//ejercicio 2
	
	private static ConjuntoTDA<Integer> llenarConjunto(int d){
		
		ConjuntoTDA<Integer> conjunto=new Conjunto<Integer>();
		conjunto.inicializarConjunto();
		
		for(int i=1; i<=d; i++){		
			conjunto.agregar(i);
		}
		
		return conjunto;
		
	}
	
	public  boolean SudokuValido(int d,MatrizTDA<Integer> m)
	{
		
		
		ConjuntoTDA<Integer> c=new Conjunto<Integer>();
		c=llenarConjunto(d);
		for(int i=0; i<d; i++){				//verifico las filas
			for(int j=0; j<d; j++){
	             if(c.pertenece(m.obtenerValor(i, j)))
	             	c.sacar(m.obtenerValor(i, j));
	             else
	            	 return false;
	        }
			c=llenarConjunto(d);
        }
		c=llenarConjunto(d);
		for(int j=0; j<d; j++){					//verifico las columnas
			for(int i=0; i<d; i++){
	             if(c.pertenece(m.obtenerValor(i, j)))
	             	c.sacar(m.obtenerValor(i, j));
	             else
	            	 return false;
	        }
			c=llenarConjunto(d);
        }
		c=llenarConjunto(d);
		
		int i,j,cuadrantei,cuadrantej;
					
		i=0;
		while (i < d)						//posicion de la fila donde empieza el cuadrante
		{
			j=0;
			while (j < d)					//posicion de la columna donde empieza el cuadrante
			{
				cuadrantej=0;
				while(cuadrantej < Math.sqrt(d))						//recorro cuadrante por columna
				{
					cuadrantei=0;
					while(cuadrantei< Math.sqrt(d)){ 				//recorro cuadrante por fila
						if(c.pertenece(m.obtenerValor(i+cuadrantei, j+cuadrantej)))
							c.sacar(m.obtenerValor(i+cuadrantei, j+cuadrantej));
						else
							return false;
						cuadrantei ++;
					}
					cuadrantej++;
				}
				j=j+(int)Math.sqrt(d);
				c=llenarConjunto(d);
			}
			i=i+(int)Math.sqrt(d);
			c=llenarConjunto(d);
		}
		return true;
	}

	//ejercicio 3
	public static void mostrarTablero(MatrizTDA<Integer> tablero,int d) {
		
		String valor;
		
		for(int i=0; i<d; i++){		
			for(int j=0; j<d; j++){		
				valor=tablero.obtenerValor(i, j).toString();
				if (valor.length()==1)
					valor=valor + " ";
				if (j==0)
				{
					System.out.println();
					System.out.print("" + valor + "  ");
				}
				else
					System.out.print("" + valor + "  ");

			}
		}
	}
	
	//ejercicio 5
	public static Posicion proximaPosicion(Posicion pos,int d) {
	
		if(pos.y == d - 1 && pos.x == d - 1  ){
			pos.y=0;		
			pos.x=0;		
		}else{
			if( pos.x < d -1 ){ //d-1
		   		pos.x += 1;
			}
			else{
		    	pos.y +=1;
		   		pos.x=0;		
			}
		}
		return pos;
	}
	
	
	// Ejercicio 8
	// agrego el objeto MResultado porque necesito un corte en el While. el jueves(Se lo consultamos al profe)
	
	public MResultado SudokuBK(int d, MResultado M, Posicion Pos,int NU, MatrizTDA<Boolean> pOcup) {
		
		MResultado MRes =new MResultado(d); /* El constructor define  a MRes.HaySol = false */
		Sudoku.mostrarTablero(M.MRes, d);
		System.out.println();
		System.out.print("-----------");

		if ( NU == (d*d)){
			if (SudokuValido(d,M.MRes)){
				MRes .HaySol = true;
				MRes .MRes = M.MRes;
			}
		}else{
			int i=1;
			while(i <= d && !MRes.HaySol){
				M.MRes.setearValor(Pos.x,Pos.y,i);
				MRes = SudokuBK(d, M,proximaPosicionDesocupada(Pos,pOcup,d), NU +1,pOcup);
				i++;
			} 
			
		}
		return MRes;
	}
	
	
	public  Posicion proximaPosicionDesocupada(Posicion pos, MatrizTDA<Boolean> MOcup, int d) {
		Posicion posAux = new Posicion();
		posAux = pos;
		pos = proximaPosicion(pos, d);
		int x= pos.x;
		int y=pos.y;
		boolean HayLibre = true;
		while(y<d && HayLibre){
			while(x<d && HayLibre){
				if(!MOcup.obtenerValor(x,y).booleanValue()){
					pos.x=x;
					pos.y=y;
					HayLibre = false;
				}
					
				x++;
			}
			y++;
			x=0;
		}
		
		if (HayLibre){
			pos = posAux;
		}
		
		return pos;
	}

   protected boolean checkCuadrante( Posicion pos, int num, MResultado M )
	   {
	   int d = M.MRes.obtenerDimension();
		d = (int) Math.sqrt(d);
		d = (int) Math.sqrt(d);
		
	      int row = (pos.x / d) * d ;
	      int col = (pos.y / d) * d ;

	      for( int r = 0; r < d; r++ )
	         for( int c = 0; c < d; c++ )
	        	 if( M.MRes.obtenerValor(row + r,col + c) == num )
	        		 return false ;

	      return true ;
	   }
	
	private  MatrizTDA<Integer> inicializaMatrizEnCero(MatrizTDA<Integer> tablero, int d){
		
		for(int i =0;i<d;i++){
			for(int j =0;j<d;j++){
				tablero.setearValor(i,j,0);	
			}
		}
		return tablero;
	}



	public MResultado ResolverSudokuBCConPoda(int d, MResultado M, Posicion Pos,int NU, MatrizTDA<Boolean> filasOcup, MatrizTDA<Boolean> colsOcup, MatrizTDA<Boolean> cuadrantesOcup) 
	{	 
		MResultado MRes = new MResultado(d); /* El constructor define  a MRes.HaySol = false */
		//int raiz = (int)Math.sqrt(d);
		if ( NU == (d*d)){
			if (SudokuValido(d,M.MRes)){
				MRes.HaySol = true;
				MRes.MRes = M.MRes;
				return MRes;
			}
		}else{
			if (M.MRes.obtenerValor(Pos.x,Pos.y) > 0) {
				MRes = ResolverSudokuBCConPoda(d, M, proximaPosicion(Pos,d), NU, filasOcup, colsOcup, cuadrantesOcup);
			} else {
				int i = 1;
				while(i <= d && !MRes.HaySol){
					if (!filasOcup.obtenerValor(Pos.x,i-1)) {
						if (checkCuadrante(Pos,i,M)) {//if (!cuadrantesOcup.obtenerValor((int)(Pos.x/raiz),(int)(Pos.y/raiz))) {// parte entera de la div ver si se hace con Raiz cuadrada
							if  (!colsOcup.obtenerValor( i-1, Pos.y)) {
								filasOcup.setearValor(Pos.x,i-1, true);
								colsOcup.setearValor(i-1, Pos.y, true);
								cuadrantesOcup.setearValor(i-1, i-1, true);
								M.MRes.setearValor(Pos.x,Pos.y,i);
								MRes = ResolverSudokuBCConPoda(d, M, proximaPosicion(Pos,d), NU + 1, filasOcup, colsOcup, cuadrantesOcup);
								if (!MRes.HaySol){
									M.MRes.setearValor(Pos.x,Pos.y,0);
									filasOcup.setearValor(i-1, Pos.y, false);// vuelvo atras los cambios
									colsOcup.setearValor(Pos.x, i-1, false);
									cuadrantesOcup.setearValor(i-1, i-1, false);
								}
							}
						}
					}
					i++;
				} 	
			}
		}
		return MRes;
	}

}
